﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0191_Template : IAlgorithm
    {
        // 946. 验证栈序列

        // 给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

        // 提示：
        //  1 <= pushed.length <= 1000
        //  0 <= pushed[i] <= 1000
        //  pushed 的所有元素 互不相同
        //  popped.length == pushed.length
        //  popped 是 pushed 的一个排列

        public void Test()
        {
            // 算法参数定义
            var pushed = new int[] { 1, 2 };
            var popped = new int[] { 1, 2 };
            // 算法执行与打印
            Console.WriteLine(ValidateStackSequences(pushed, popped));
        }

        // 算法
        // pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
        // [1,2,3,4,5] [4,5,3,2,1]

        public bool ValidateStackSequences(int[] pushed, int[] popped)
        {
            Stack<int> stack = new Stack<int>();
            int n = pushed.Length;
            for (int i = 0, j = 0; i < n; i++)
            {
                stack.Push(pushed[i]);
                while (stack.Count > 0 && stack.Peek() == popped[j])
                {
                    stack.Pop();
                    j++;
                }
            }
            return stack.Count == 0;
        }
    }
}
